home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 11 / Cream of the Crop 11-1.iso / windows / boyer04.zip / BOYER.DOC < prev    next >
Text File  |  1996-01-14  |  11KB  |  256 lines
  1. -------------------------------------------------------------------------------
  2.       Fast String Search Algorithm (Boyer) for Windows C/C++ Programmers
  3.                               version 0.4
  4.                          (Supports Windows 3.x)
  5.  
  6.                           by Patrick KO Shu-pui
  7.  
  8.                 Copyright (c) 1991-1996 All Rights Reserved.
  9. -------------------------------------------------------------------------------
  10.  
  11. ===============================================================================
  12. 0. INTRODUCTION
  13. ===============================================================================
  14. This document only provides you the following information:
  15.  
  16.         0.1     Description of the Boyer-Moore Function Calls
  17.         0.2     How to use Boyer-Moore functions in your program
  18.         0.3     Questions and Answers
  19.         0.4     References to the Boyer-Moore Algorithm
  20.  
  21. ===============================================================================
  22. 1. Boyer-Moore Function Calls
  23. ===============================================================================
  24. Reference of Search Model: (For Clarity)
  25.  
  26. Problem solved by Boyer-Moore:
  27.  
  28.         Let p, s be strings, and length of p = m, length of s = n.
  29.  
  30.         For a pattern p, find the position i in search space s where
  31.         p[0] = s[i], p[1] = s[i+1], ... p[m-1] = s[i+m-1].
  32.  
  33. Time Complexity of Boyer-Moore Algorithm:
  34.  
  35.         On "average" case, it takes n/m steps to find p in s.
  36.  
  37. -------------------------------------------------------------------------------
  38. Function :      SetFindPattern()
  39. Synopsis :      initialize the pattern to be matched, this function must be
  40.                 called prior to Find() and FindBackward().
  41.  
  42. Parameter:      LPSTR p = pattern string to be matched
  43. Return Value:   HFIND = a find handle
  44. Example:
  45.                 HFIND hfind;
  46.                 LPSTR pattern = "find me";
  47.  
  48.                 hfind = SetFindPattern( pattern );
  49.                 ...
  50.  
  51.  
  52. See Also:       FreeFindPattern()
  53. -------------------------------------------------------------------------------
  54. Function :      Find()
  55. Synopsis :      Find a pattern inside a string from s[0] to s[n-1]
  56.  
  57. Parameter:      HFIND hfind = the find handle obtained from SetFindPattern()
  58.                 LPSTR s = pointer to the start of string to be searched
  59.                 LONG slen = length of the string s (i.e. n)
  60.  
  61. Return Value:   NULL = pattern not found in string s
  62.                 non NULL = pointer within s where pattern is matched
  63.                            at first position (i.e. p[0])
  64.  
  65. Example:        To find a pattern "tiger" in a text in RAM starting at
  66.                 pointer "txtp" with a length of 1,000,000 characters,
  67.                 program like this:
  68.  
  69.                 HFIND hfind;
  70.                 LPSTR matchp;
  71.                 LPSTR txtp;
  72.  
  73.                 /* allocate memory for txtp */
  74.                 ...
  75.                 if ((hfind = SetFindPattern( "tiger" )) != (HFIND)NULL)
  76.                 {
  77.                         matchp = Find( hfind, txtp, 1000000L );
  78.                         if (matchp != NULL)
  79.                         /* found */
  80.                         else
  81.                         /* not found */
  82.                         ...
  83.                 }
  84.  
  85.                 ... use hfind many times until finish with it then free ...
  86.                 FreeFindPattern(hfind);
  87.  
  88. See Also:       SetFindPattern(), FindIC(), FindBackward(), FindBackwardIC()
  89. -------------------------------------------------------------------------------
  90. Function :      FindBackward()
  91. Synopsis :      Find a pattern inside a string from s[n-1] to s[0]
  92.  
  93. Parameter:      HFIND hfind = the find handle obtained from SetFindPattern()
  94.                 LPSTR s = pointer to the start of string to be searched
  95.                 LONG slen = length of the string s (i.e. n)
  96.  
  97. Return Value:   NULL = pattern not found in string s
  98.                 non NULL = pointer within s where pattern is matched
  99.                            at first position (i.e. p[0])
  100.  
  101. Example:        To find a pattern "tiger" in a text in RAM starting at
  102.                 end of pointer "txtp" with a length of 1,000,000
  103.                 characters, program like this:
  104.  
  105.                 HFIND hfind;
  106.                 LPSTR matchp;
  107.                 LPSTR txtp;
  108.  
  109.                 /* allocate memory for txtp */
  110.                 ...
  111.  
  112.                 if ((hfind = SetFindPattern( "tiger" )) != (HFIND)NULL)
  113.                 {
  114.                         matchp =
  115.                         FindBackward( hfind, txtp + 1000000L - 1, 1000000L);
  116.                         if (matchp != NULL)
  117.                         /* found */
  118.                         else
  119.                         /* not found */
  120.                 }
  121.  
  122.                 ... use hfind many times until finish with it then free ...
  123.                 FreeFindPattern(hfind);
  124.  
  125. See Also:       SetFindPattern(), Find(), FindIC(), FindBackwardIC()
  126. -------------------------------------------------------------------------------
  127. Function :      FindIC()
  128. Synopsis :      Find a pattern inside a string from s[0] to s[n-1]
  129.                 and ignore case
  130.  
  131. Parameter:      HFIND hfind = the find handle obtained from SetFindPattern()
  132.                 LPSTR s = pointer to the start of string to be searched
  133.                 LONG slen = length of the string s (i.e. n)
  134.  
  135. Return Value:   NULL = pattern not found in string s
  136.                 non NULL = pointer within s where pattern is matched
  137.                            at first position (i.e. p[0])
  138.  
  139. Example:        To find a pattern "tiger" in a text in RAM starting at
  140.                 pointer "txtp" with a length of 1,000,000 characters,
  141.                 program like this:
  142.  
  143.                 HFIND hfind;
  144.                 LPSTR matchp;
  145.                 LPSTR txtp;
  146.  
  147.                 /* allocate memory for txtp */
  148.                 ...
  149.                 if ((hfind = SetFindPattern( "tiger" )) != (HFIND)NULL)
  150.                 {
  151.                         matchp = FindIC( hfind, txtp, 1000000L );
  152.                         if (matchp != NULL)
  153.                         /* found */
  154.                         else
  155.                         /* not found */
  156.                         ...
  157.                 }
  158.  
  159.                 ... use hfind many times until finish with it then free ...
  160.                 FreeFindPattern(hfind);
  161.  
  162. See Also:       SetFindPattern(), Find(), FindBackward(), FindBackwardIC()
  163. -------------------------------------------------------------------------------
  164. Function :      FindBackwardIC()
  165. Synopsis :      Find a pattern inside a string from s[n-1] to s[0]
  166.                 and ignore case
  167.  
  168. Parameter:      HFIND hfind = the find handle obtained from SetFindPattern()
  169.                 LPSTR s = pointer to the start of string to be searched
  170.                 LONG slen = length of the string s (i.e. n)
  171.  
  172. Return Value:   NULL = pattern not found in string s
  173.                 non NULL = pointer within s where pattern is matched
  174.                            at first position (i.e. p[0])
  175.  
  176. Example:        To find a pattern "tiger" in a text in RAM starting at
  177.                 end of pointer "txtp" with a length of 1,000,000
  178.                 characters, program like this:
  179.  
  180.                 HFIND hfind;
  181.                 LPSTR matchp;
  182.                 LPSTR txtp;
  183.  
  184.                 /* allocate memory for txtp */
  185.                 ...
  186.  
  187.                 if ((hfind = SetFindPattern( "tiger" )) != (HFIND)NULL)
  188.                 {
  189.                         matchp =
  190.                         FindBackwardIC( hfind, txtp + 1000000L - 1, 1000000L);
  191.                         if (matchp != NULL)
  192.                         /* found */
  193.                         else
  194.                         /* not found */
  195.                 }
  196.  
  197.                 ... use hfind many times until finish with it then free ...
  198.                 FreeFindPattern(hfind);
  199.  
  200. See Also:       SetFindPattern(), Find(), FindIC(), FindBackward()
  201. -------------------------------------------------------------------------------
  202. ===============================================================================
  203. 2.      Questions and Answers
  204. ===============================================================================
  205.     Q:      How can I use Boyer-Moore functions in my Windows program?
  206.     A:      Compile boyer.c into object file and link with your program.
  207.  
  208.     Q:      How can I use Boyer-Moore functions in other Windows
  209.             frontend toolkits such as SQLWindows(tm), PowerBuilder(tm),
  210.             Visual Basic(tm), etc.?
  211.     A:      Boyer-Moore functions are also provided in form of DLL,
  212.             which can be called from these toolkits.
  213.  
  214.     Q:      Can I use Find() and FindBackward() with a GlobalLock()
  215.             pointer in Windows?
  216.     A:      Yes.
  217.  
  218.     Q:      Must I delcare my pointer as HPSTR (huge pointer) ?
  219.     A:      Not necessary.  Find() and FindBackward() will convert your
  220.             LPSTR as HPSTR.  However, in your own code you must aware
  221.             that you are holding a LPSTR and take care of the pointer
  222.             arithmetic and conversion. (see demo.c for example)
  223.  
  224.     Q:      What is the limit of the memory space I can search?
  225.     A:      To the limit of huge pointer implementation and your hardware.
  226.  
  227.     Q:      When I use the BOYER.DLL, can the Find() functions be shared
  228.             by multiple applications?
  229.     A:      Yes, as long as you bare the mind that BOYER.DLL functions
  230.             are not "handle" type function calls, i.e. BOYER.DLL do not
  231.             requires you to acquire a handle first and free a handle later,
  232.             which implies that a sequence of SetFindPattern(), Find() calls
  233.             can not interleave in multiple applications, which causes
  234.             the global data to corrupt.
  235.  
  236.      Q:     Does BOYER.DLL supports other data model other than LARGE?
  237.      A:     All sources are provided as is and you can modify it for
  238.             your own model once you become a registered user.  Send a
  239.             email to the author for other data models if you really want
  240.             it mad and do not want to modify the source code yourself.
  241.  
  242.      Q:     Does BOYER.DLL or BOYER.LIB supports multi-threaded search?
  243.      A:     Yes, start from v0.4 BOYER allows the program to create a
  244.             HFIND handle for doing a search, where multiple HFIND handles
  245.             could be created at run-time in the same program or across
  246.             programs.
  247. ===============================================================================
  248. 3.      References
  249. ===============================================================================
  250.         "Algorithms". Robert Sedgewick. Addison Wesley Publishing Company.
  251.         1988. 2nd addition. p286. QA76.6.S435 1983
  252.  
  253.         "Faster String Searches". Doctor Dobb's Journal. Volume 14
  254.         Issue 7 July 1989. Costas Menico. p74.
  255. -------------------------------------------------------------------------------
  256.